/**
 * @param {number[]} queries
 * @param {number} intLength
 * @return {number[]}
 */
 var kthPalindrome = function(queries, intLength) {
  let cnt = 9
  for(let i = 1; i<intLength/2; i++) {
    cnt *= 10
  }
  const m = Math.max(...queries)
  cnt = Math.min(cnt, m)
  const pq = new PriorityQueue()
  const g = {}
  const INIT = new Array(intLength).fill(0)
  INIT[0] = 1
  if(intLength >= 2) {
    INIT[intLength-1] = 1
  }
  return queries.map(q => {
    if(q-1 > cnt) return -1
    let arr = []
    while(pq.size && pq.peek() > q) {
      arr.push(pq.pop())
    }
    let now
    if(pq.size) {
      let x = pq.pop()
      arr.push(x)
      const t = String(g[x]).split('').map(v => Number(v))
      now = getMin(t, q-x)
    } else {
      now = getMin([...INIT], q)
    }
    while(arr.length) {
      pq.push(arr.pop())
    }
    g[q] = now
    return now
  })
  function getMin(t, q) {
    for(let i = 0; i<q-1; i++) {
      for(let j = Math.floor((intLength-1)/2); j>=0; j--) {
        let c = t[j]
        if(c < 9) {
          t[j] = c+1
          if(intLength-j-1 > j) {
            t[intLength-j-1] = c+1
          }
          break
        } else {
          if(j !== 0) {
            t[j] = 0
            if(intLength-j-1 > j) {
              t[intLength-j-1] = 0
            }
          }
        }
      }
    }
    return BigInt(t.join(''))
  }
};

// 优先队列
class PriorityQueue {
  // 默认最大堆
  constructor(
    compare = (a, b) => a > b 
    ){
    this.data = []
    this.size = 0
    this.compare = compare
  }

  peek() {
    return this.size === 0 ? null : this.data[0] 
  }

  push(val) {
    this.data.push(val)
    this._shifUp(this.size++)
  }

  pop() {
    if(this.size === 0) { return null }
    this._swap(0, --this.size)
    this._shifDown(0)
    return this.data.pop()
  }

  _parent(index) {
    return index - 1 >> 1
  }
  
  _child(index) {
    return (index << 1) + 1
  }

  _shifDown(index) {
    while(this._child(index) < this.size) {
      let child = this._child(index)
      if(child + 1 < this.size 
        && this.compare(this.data[child + 1], this.data[child])) {
          child = child + 1
      }
      if(this.compare(this.data[index], this.data[child])){
        break
      }
      this._swap(index, child)
      index = child
    }
  }

  _shifUp(index) {
    while(this._parent(index) >= 0 
    && this.compare(this.data[index], this.data[this._parent(index)])) {
      this._swap(index, this._parent(index))
      index = this._parent(index)
    }
  }

  _swap(a, b) {
    [this.data[a], this.data[b]] = [this.data[b], this.data[a]]
  }
}